#define _CRT_SECURE_NO_WARNINGS 1	

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>

//KMP算法

void getNext(char* str, int* next, int len)
{
    assert(next && str);
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int k = 0;
    while (i < len)
    {
        if (k == -1 || str[i - 1] == str[k])
        {
            next[i] = k + 1;
            i++;
            k++;
        }
        else
        {
            k = next[k];
        }
    }
}

int KMP(char* str, char* sub, int pos)
{
	//KMP
	//str:主串   sub:子串
	assert(str && sub);

	size_t strLen = strlen(str);
	size_t subLen = strlen(sub);

	if (subLen > strLen || strLen == 0 || subLen == 0)
		return -1;
	if (pos < 0 || pos >= strLen)
		return -1;

	//构建数组
	int* next = (int*)calloc(subLen, sizeof(int));
	assert(next);

	//获取 next 数组
	getNext(sub, next, subLen);

	size_t i, j;
	i = pos;
	j = 0;
	while (i < strLen && j < subLen)
	{
		if (next[j] == -1 || str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			//回退
			j = next[j];
		}
	}

	//只有相等，才有可能匹配成功
	if (j == subLen)
	{
		return i - j;
	}

	return -1;
}
int main()
{
    printf("%d\n", KMP("ababcabcdabcde", "abcd", 0)); //5
    printf("%d\n", KMP("ababcabcdabcde", "abcdf", 0)); //-1
    printf("%d\n", KMP("ababcabcdabcde", "ab", 0)); //0

    printf("%d\n", KMP("", "", 0)); //5

    return 0;
}